(1) Field of the Invention
The present invention relates to scheduling of autonomous agents. More particularly, the present invention relates to scheduling and route planning operations for transport agents and service agents.
(2) Description of the Prior Art
The use of autonomous systems to perform increasingly complex and coordinated tasks has necessitated creating heterogeneous teams of agents, where different agent types specialize in different parts of an operation. One such heterogeneous team operation includes a mobile agent, or service agent, tasked with performing the direct servicing tasks for the operation. A larger, faster-moving, or longer-range agent, referred to herein as a transport agent, is responsible for transporting the service agents between jobs for faster completion.
Within manned systems, there are numerous examples of the transport agent/service agent concept such as aircraft carriers and their respective aircraft, garbage trucks and accompanying garbage workers, or mail delivery vehicles and their respective postmen. While this form of close interaction between unmanned systems is still far from common, the underlying hardware and guidance infrastructure to allow autonomous docking and deployment between unmanned systems are being researched for a variety of different applications.
Just as important as the fundamental infrastructure of docking and deploying unmanned systems autonomously is determining the most efficient schedule for when and where to perform these actions when multiple agents can be assigned to perform an operation. Indeed, new methods of package delivery such as cooperative teams of aerial drones and shipping trucks are being explored by leading technology companies. Furthermore, cooperative teams of unmanned underwater vehicles (UUVs) and unmanned surface vessels (USVs) are quickly emerging where one unit performs the substantive survey operations while the other is used for transportation and refueling.
The problem of scheduling and task allocation has been extensively studied with a variety of techniques in multiple forms. As an example, a coordination architecture for modeling multi-robot coordination and task allocation has been developed. However, this methodology limits the types of scenarios under which a constraint optimization framework can be used. The methodology is inadequate for problems where there are strongly coupled constraints on agents such as transportation actions.
Frameworks to explore optimal vehicle routing with cross-schedule constraints with applications to robotic assistance have also been investigated. However, the principal element of optimization is an agent route, not the collection of agent actions comprising the route. Additionally, in considering the route optimization problem, individuals being transported along the routes are static in such frameworks. There is no mechanism within the optimization framework for the individuals themselves to move about the area. As such, these frameworks are similar to the traditional vehicle routing problem.
Other examples of prior work in these areas have addressed the problem of finding the shortest route for paired agents. In one, the pairing consisted of an unmanned ground vehicle and an unmanned aerial vehicle (UAV) pair to transit and make deliveries to locations only reachable by the UAV. In another, the pairing involved an aircraft carrier and an aerial vehicle. However, both these works focused primarily on the overall path planning for the two vehicles, and not on fuel limitations and the higher-level scheduling aspects required when there is an arbitrary number of each vehicle type.
Other research in this area has developed a centralized algorithm to efficiently schedule manufacturing processes using robotic teams. However, the work is primarily focused on the development of a novel task sequencing heuristic that allows a simple temporal problem, coupled with simple spatial-temporal constraints, to be tractable for large numbers of tasks and robots to be assigned to a fixed set of tasks. The algorithm schedules deterministic problems, but does not handle scheduling uncertainty for the agents, where the agents may choose from a number of different docking, deployment, and movement actions to allow a location to be serviced. Also, cross-schedule constraints between the chosen actions and the transport agents are not addressed.
General robust scheduling techniques have been studied using a variety of methods. Complimentary approaches to formally incorporate uncertainty in scheduling problems have been developed. For example, formal methodologies have been developed for converting mixed-integer linear programming (MILP) scheduling problems, where model parameters are uncertain under either a bound or known probability distribution, into another MILP or mixed-integer non-linear programming (MINLP) type problem, where the uncertainty is explicitly incorporated into the optimization framework. These types of methodologies can yield a robust solution that still meets the problem constraints with a fixed probability.
In a similar manner, others have created methods to adjust the conservatism of robust MILP solutions while keeping the robust problem linear. Further work on robust scheduling and integer programming problems in the general sense can also be found. However, there appears to be no current work for explicitly incorporating Bayes risk to schedule slips, or for the application of service agent-transport agent scheduling.
Thus, a need has been recognized in the state of the art to develop agent scheduling methods which can operate when there are strongly coupled constraints on agents. The method needs to consider the collection of agent actions comprising the route and not just an agent route. Additionally, there needs to be a mechanism within the optimization framework for the individuals themselves to move about the area.
Further, the method needs to consider fuel limitations and the higher-level scheduling aspects required when there is an arbitrary number of each vehicle type. The method need to handle scheduling uncertainty for the agents and the agents need to be able to choose from a number of different docking, deployment, and movement actions to allow a location to be serviced. Also, the method needs to consider cross-schedule constraints between the chosen actions and the transport agents.